package MaxHeap;
import java.util.Arrays;
public class MaxHeap {
    int[] array;
    int size;

    public MaxHeap(int capacity){ this.array = new int[capacity];}
    public MaxHeap(int[] array){
        this.array = array;
        this.size = array.length;
        heapify();
    }
    private void heapify(){
        for (int i = size / 2 - 1; i >= 0 ; i--) {
            down(i);
        }
    }
    //删除堆顶元素
    //Returns：堆顶元素
    public int poll() throws EmptyHeapException{
        if(isEmpty()){
            throw new EmptyHeapException("Heap is Empty");
        }
       int top = array[0];
       swap(0,size-1);
       size--;
       down(0);
       return top;
    }
    //删除指定索引处元素
    public int poll(int index) throws EmptyHeapException{
        if (isEmpty()){
            throw new EmptyHeapException("Heap is Empty");
        }
        int deleted = array[index];
        swap(index,size-1);
        size--;
        down(index);
        return deleted;
    }
    //获取堆顶元素
    public int peek() throws EmptyHeapException {
        if(isEmpty()){
            throw new EmptyHeapException("Heap is Empty");
        }
        return 0;
    }
    //替换堆顶元素
    public void replace(int replaced){
        array[0] = replaced;
        down(0);
    }
    //堆的尾部添加元素
    public boolean offer(int offered){
        if(size == array.length){
            return false;
        }
        up(offered);
        size++;
        return true;
    }
    //将inserted元素上浮：直至offered小于父元素或到堆顶
    private void up(int offered){
         int child = size;
         while(child > 0){
             int parent = (child - 1)/2;
             if(offered >  array[parent]){
                 array[child] = parent;
             }else{
                 break;
             }
             child = parent;
         }
         array[child] = offered;
    }
    public boolean isEmpty(){
        return size == 0;
    }
    class EmptyHeapException extends Exception {
        public EmptyHeapException(String message) {
            super(message);
        }
    }
    //将parent索引处的元素下潜：与两个孩子较大者交换，直至没孩子或者没它大
    private void down(int parent){
        int left = parent * 2 + 1;
        int right = left + 1;
        int max = parent;
        if(left < size && array[left] > array[max]){
            max = left;
        }
        if(right < size && array[right] > array[max]){
            max = right;
        }
        if(max != parent){
            swap(max,parent);
            down(max);
        }
    }
    //交换两个索引处的元素
    private void swap(int i,int j){
            int t = array[i];
            array[i] = array[j];
            array[j] = t;
    }

    public static void main(String[] args) {
        int[] array = {1,2,3,4,5,6,7};
        MaxHeap maxHeap = new MaxHeap(array);
        System.out.println(Arrays.toString(maxHeap.array));
    }
}
